// depSolve.cpp

#include <limits>
#include <iostream>
#include <llvm/ADT/APSInt.h>
#include "depSolve.h"
#include "DepGraph.h"

#define DEP_DEBUG

using namespace std;

/** Build a dependency graph using information about array reads and writes. */
DepGraph generateDependencyGraph(LoopNestInfo loopInfo) {

    // SAMPLE CODE FOR TRAVERSING THE READS AND WRITES.
    std::vector<SubscriptExpr>::iterator readiter;
    std::vector<SubscriptExpr>::iterator writeiter;
    std::vector<SubscriptExpr>::iterator writeiter2;

    // create empty graph?
    // create nodes first
    int numNodes = loopInfo.nStatements();
    //    GraphNode node[numNodes]; // statement i is at location i in the array
    
    // add these nodes to the graph
    DepGraph depGraph(numNodes);
    std::vector<std::vector<int> > adjList;
    // REPL
    adjList.resize(numNodes);
    for(int i = 0; i < numNodes; i++) {
      adjList[i].resize(numNodes);
    }

    llvm::APSInt lbound = loopInfo.lbound();
    llvm::APSInt ubound = loopInfo.ubound();

    for (writeiter = loopInfo.writes.begin();
         writeiter < loopInfo.writes.end();
         writeiter++) {
      int writeStmtIndex = writeiter->stmtIndex;

        for (readiter = loopInfo.reads.begin();
             readiter < loopInfo.reads.end();
             readiter++) {
            // your analysis goes here.
	  // single statement, no dependencies
	  // same coeff, array, stmt, then don't need to check for dep - REPL
	  std::string writeArrayName = writeiter->arrayName;
	  std::string readArrayName = readiter->arrayName;
	  int readStmtIndex = readiter->stmtIndex;
	  llvm::APSInt writeCoeffs1 = writeiter[0][0];
	  llvm::APSInt writeCoeffs2 = writeiter[0][1];
	  llvm::APSInt readCoeffs1 = readiter[0][0];
	  llvm::APSInt readCoeffs2 = readiter[0][1];

	  // a[i] = a[i] + 1
	  if(writeArrayName == readArrayName && writeStmtIndex == readStmtIndex && writeCoeffs1 == readCoeffs1 && writeCoeffs2 == readCoeffs2) {
	    continue; // for now, assuming that we needn't initialize adjList
	  }

	  if(dependent(*readiter, *writeiter, lbound, ubound)) { // anti-dep
	    continue; // same assumption as above case
	  }

	  if(dependent(*writeiter, *readiter, lbound, ubound)) { // true dep
	    adjList[writeStmtIndex][readStmtIndex] = 1;
	  }
        }
        // and here.

	// check output dependence
        for (writeiter2 = loopInfo.writes.begin();
             writeiter2 < loopInfo.writes.end();
             writeiter2++) {
	  int writeStmtIndex2 = writeiter2->stmtIndex;
	  if(writeiter == writeiter2) {
	    continue;
	  }else if(dependent(*writeiter, *writeiter2, lbound, ubound)) {
	    adjList[writeStmtIndex][writeStmtIndex2] = 1;
	  }
	}
    }

    // assign to depGraph.adjList
    depGraph.setAdjList(adjList);

    return depGraph;
}

bool antiDep() {
  return true;
}
/** Add your own methods to traverse the graph. */
    
/** Check dependency between just two single-subscript array accesses.
    Assumes loop counts upward. */
bool dependent(SubscriptExpr access1, SubscriptExpr access2,
               llvm::APSInt lbound, llvm::APSInt ubound) {

    // default to unprovable if more than one subscript in use
    if (access1.size() > 2) return true; 

    // if array names are different, no dependency.
    if (access1.arrayName != access2.arrayName) return false;
    
    // first case: ziv (only constant subscript)
    if (access1.size() == 1 || (access1[1] == 0 && access2[1] == 0)) {
        if (access1[0] == access2[0]) return true;
        else return false; // unequal, no dependency
    }

    // weak-zero SIV. 
    else if (access2[1] == 0) {
        if (access2[0] < lbound || access2[0] > ubound) return false;
        else return true;
    }
    else if (access1[1] == 0) {
        if (access1[0] < lbound || access1[0] > ubound) return false;
        else return true;
    }

    // strong SIV, same coefficients
    else if (access1[1] == access2[1]) {
        if (access2[0] == access1[0]) { // equal constants, loop-invariant
            return true; 
        }
        else if (access2[0] < access1[0]) { // loop-dependent, access1-after-access2 (flow)
            if ((access1[0] - access2[0]) <= (ubound - lbound)) return true;
            else return false;
        }
        else return false; 
    }
    
    // This statement should not be reached.
    return true;
}
